package Acwing;

public class Acwing14 {
    public static int duplicateInArray(int[] nums) {
        int n= nums.length;
        //抽屉原理   分治思想
        int l = 1, r = n-1;
        while(l < r){
            int mid = (l + r)/2;  // 划分的区间：[l, mid], [mid + 1, r]

            int count=0; //个数

            for(int x : nums){ //x为数组中的值
                if(x >= l && x <= mid){
                    ++count;
                }
            }

            if (count > mid - l + 1) {//左区间个数多
                r = mid; //左区间
            } else {
                l = mid + 1; //右区间
            }
        }
        return r;
    }
    public static void main(String[] args) {

        int[] num={1,3,2,2,4};

        System.out.println(duplicateInArray(num));
    }
}
